#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
using namespace std;

namespace lh
{
	//BM42 用两个栈实现队列
	//https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=295&tqId=23281&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution
    {
    public:
        void push(int node) {
            st.push(node);
        }

        int pop() {
            //元素全放入出栈，此时出栈的栈顶元素就是入栈的栈底元素，也就是队列头
            while (!st.empty())
            {
                pst.push(st.top());
                st.pop();
            }
            int temp = pst.top();
            pst.pop();
            //删完再重新放回入栈，保证元素入栈的顺序不变
            while (!pst.empty())
            {
                st.push(pst.top());
                pst.pop();
            }
            return temp;
        }

    private:
        stack<int> st; //入栈 
        stack<int> pst;//出栈
    };


    //BM43 包含min函数的栈
    //https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=295&tqId=23268&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        void push(int value) {
            st.push(value);
            //Minst为空或者Minst的栈顶大于等于value，Minst入栈value
            if (Minst.empty() || value <= Minst.top())
            {
                Minst.push(value);
            }
        }
        void pop() {
            if (st.top() == Minst.top())
            {
                Minst.pop();
            }
            st.pop();
        }
        int top() {
            return st.top();
        }
        int min() {
            return Minst.top();
        }
    private:
        stack<int>st;
        stack<int>Minst;//最小栈，放最小的元素
    };

    //BM44 有效括号序列
    //https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tqId=726&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution3 {
    public:

        bool isValid(string s) {
            stack<char>st;
            for (auto ch : s)
            {
                if (ch == '{')
                    st.push('}');
                else if (ch == '(')
                    st.push(')');
                else if (ch == '[')
                    st.push(']');
                //必须有左括号才能进行匹配右括号
                else if (st.empty())
                    return false;
                //右括号匹配弹出
                else if (st.top() == ch)
                {
                    st.pop();
                }
            }
            return st.empty();

        }
    };
}